package com.leetcode.search;

import java.util.Arrays;

public class NextPermutation {
    public void nextPermutation(int[] nums) {
        // 从后向前遍历得到第一对升序对【i-1, i】
        // 对尾部的降序队列【i, end】进行重新排序
        // 选取第一个比i-1大的数进行交换
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] >= nums[i]) {
                continue;
            }
            // 得到第一个升序对
            // sort方法左闭右开
            Arrays.sort(nums, i, nums.length);
            for (int j = i; j < nums.length; j++) {
                if (nums[j] > nums[i - 1]) {
                    swap(nums, j, i - 1);
                    return;
                }
            }
        }
        // 不存在时排列成最小的（升序）
        Arrays.sort(nums);
    }

    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public static void main(String[] args) {
        // Integer[] nums = new Integer[]{ 1, 2, 3, 4, 5 };
        // Arrays.sort(nums, (x, y) -> y - x);
        // System.out.println(Arrays.asList(nums));

        // List<Integer> myList = new ArrayList<Integer>();
        // for (int i = 0; i < 10; i++)
        //     myList.add(i);
        // myList.forEach(System.out::println);
    }
}
